package tree;


import com.sun.istack.internal.NotNull;
import sun.misc.Queue;

import java.util.LinkedList;

/**
 * 链表实现
 *
 * @param <K>
 * @param <V>
 */
public class BinaryTree<K extends Comparable<K>, V> {

    //记录根结点,链表的头结点
    private Node<K, V> root;
    //记录树中元素的个数
    private int N;

    //获取树中元素的个数
    public int size() {
        return N;
    }

    public void put(K key, V value) {
        root = put(root, key, value);
    }

    //针对某一个树的根节点进行put，并返回新的根节点
    private Node<K, V> put(Node<K, V> node, K key, V value) {
        //树空
        if (node == null) {
            N++;
            return new Node<K, V>(key, value, null, null);
        }

        int cmp = key.compareTo(node.key);
        if (cmp > 0) {
            node.right = put(node.right, key, value);
        } else if (cmp < 0) {
            node.left = put(node.left, key, value);
        } else {
            node.value = value;

        }

        return node;
    }

    public V get(K key) {
        return get(root, key);
    }

    ;

    private V get(Node<K, V> node, K key) {
        if (node == null) {
            return null;
        }
        int cmp = key.compareTo(node.key);
        if (cmp > 0) {
            return get(node.right, key);
        } else if (cmp < 0) {
            return get(node.left, key);
        } else {
            return node.value;
        }
    }

    ;

    public void delete(K key) {
        root = delete(root, key);
    }

    ;

    //只需要返回子树的根节点即可
    private Node<K, V> delete(Node<K, V> node, K key) {
        if (node == null) return null;
        int cmp = key.compareTo(node.key);
        if (cmp > 0) {
            node.right = delete(node.right, key);
        } else if (cmp < 0) {
            node.left = delete(node.left, key);
        } else {
            //删除涉及树的调整
            if (node.left == null) {
                return node.right;
            }

            if (node.right == null) {
                return node.left;
            }

            Node<K, V> minNode = node.right;
            //如果右子树无左分支
            if (minNode.left == null) {
                minNode.left = node.left;
                return minNode;
            }
            Node<K, V> fatherMinNode = null;
            //找到删除的节点右子树的做小节点
            while (minNode.left != null) {
                fatherMinNode = minNode;
                minNode = minNode.left;
            }
            //删除最小节点与父亲的连接，避免成环
            fatherMinNode.left = null;
            minNode.left = node.left;
            minNode.right = node.right;
            //新的节点不需要与它的原来父节点连接，直接返回子树的头结点即可，连接在调用的方法中体现
            node = minNode;
            N--;
        }

        return node;
    }

    public K min(){
        return min(root).key;
    }

    private Node<K,V> min(Node<K,V> node){
        if (node.left==null) return node;
        return min(node.left);
    }

    //找出整个树中最大的键
    public K max(){
        return max(root).key;
    }

    //找出指定树x中最大键所在的结点
    public Node<K,V> max(Node<K,V> x){
        if (x.right!=null){
            return max(x.right);
        }else{
            return x;
        }
    }

    //使用前序遍历，获取整个树中的所有键
    public LinkedList<Node<K,V>> preErgodic(){
        LinkedList<Node<K,V>> queue = new LinkedList<>();
        preErgodic(root,queue);
        return queue;

    }

    private void preErgodic(Node<K,V> node, LinkedList<Node<K,V>> queue) {
        if (node==null) return;

        queue.add(node);
        if (node.left!=null) preErgodic(node.left,queue);

        if (node.right!=null)  preErgodic(node.right,queue);
    }

    /**
     * 层次遍历
     * @return
     */
    public LinkedList<Node<K,V>> layerErgodic(){
        LinkedList<Node<K,V>> mid = new LinkedList<>();
        LinkedList<Node<K,V>> res = new LinkedList<>();
        mid.add(root);
        while (!mid.isEmpty()){
            //每弹出一个节点，就把它的左右子节点都入队
            Node<K, V> node = mid.removeFirst();
            res.add(node);
            if (node.left!=null) mid.add(node.left);

            if (node.right!=null) mid.add(node.right);

        }
        return res;
    }

    //计算整个树的最大深度
    public int maxDepth() {
        return maxDepth(root);
    }
    private int maxDepth(Node<K,V> node){
        if (node == null) {
            return 0;
        }
        int max=0;
        int maxL=0;
        int maxR=0;
        if (node.left!=null) maxL=maxDepth(node.left);
        if (node.right!=null) maxR=maxDepth(node.right);
        max=maxL>maxR?maxL+1:maxR+1;
        return max;
    }


}
